#include "NFAtoDFA.h"

using namespace std;
using namespace std::tr1;


/// Constructors
NFAtoDFAConversion::NFAtoDFAConversion(shared_ptr<NondeterministicFiniteAutomaton> nfa): _nfa(nfa)
{
}

/// Destructors

bool isEmptyState(const vector<bool>& state)
{
	return find(state.begin(), state.end(), true) != state.end();
}

static string toString(const vector<bool>& state)
{
	string ret;
	
	for (vector<bool>::const_iterator it = state.begin(); it != state.end(); ++it)
		ret+= *it ? "1" : "0";
		
	return ret;
}

static vector<bool> toState(const string& str)
{
	vector<bool> ret;
	
	for (string::const_iterator it = str.begin(); it != str.end(); ++it)
		ret.push_back(*it == '1' ? true : false);
	
	return ret;
}

void NFAtoDFAConversion::initDfa()
{
	unsigned n = _nfa->getSize();
	dfa.reset(new DeterministicFiniteAutomaton(1));

	

	vector<bool> firstState(n);
	firstState[0] = true;
	firstState = _nfa->lambda_closure(firstState);
	states[toString(firstState)] = 0;

	newStates.push_back(make_pair(toString(firstState), 0U));
	
}

bool NFAtoDFAConversion::isFinal(const string& stateStr)
{   
    bool isFinal;
    for (unsigned i = 0; i < stateStr.size() && !isFinal; ++i)
    {
        bool isOn = stateStr[i] == '1';
        isFinal = isOn && _nfa->isFinal(i);
    } 
    return isFinal;
}


void NFAtoDFAConversion::setFinalStates()
{
    for (map<std::string, int>::const_iterator it = states.begin(); it != states.end(); ++it)
    {
        if (this->isFinal(it->first))
            dfa->addAsFinalState(it->second);
    }
}


shared_ptr<DeterministicFiniteAutomaton> NFAtoDFAConversion::getDfa()
{
    typedef vector<pair<string, unsigned> > statesVector;
    
    initDfa();
    
	unsigned n = _nfa->getSize();	
	const set<char>& alphabet = _nfa->alphabet();
	
	//bool newStates = false;

	
	do
	{
		vector<pair<string,unsigned> > lastAddedStates(newStates);
		newStates.clear();

		for (statesVector::const_iterator statesIt = lastAddedStates.begin(); statesIt != lastAddedStates.end(); ++statesIt)
		{
			vector<bool> currentState = toState(statesIt->first);
			for(set<char>::const_iterator it = alphabet.begin(); it != alphabet.end(); ++it)
			{
				char character = *it;
				vector<bool> nextState = _nfa->transition(currentState, character);
				string nextStateStr = toString(nextState);
				
				if (nextStateStr.empty())
					continue;
				
				/// Si es un estado nuevo, lo agrego al mapa	
				if (states.find(nextStateStr) == states.end())
				{
				    int newIndex = dfa->addState();
					newStates.push_back(make_pair(nextStateStr, static_cast<unsigned>(newIndex)));
					states[nextStateStr] =	newIndex;
				}
				
				dfa->addTransition(statesIt->second,states[nextStateStr], character);
				
			}
		}
		
	}while(newStates.size() > 0);
    
    setFinalStates();
	return dfa;
}
